package game;

/**
 * 给一个数组代表火柴棍的长度，将这些火柴能拼成一个正方形嘛？
 * eg1: [3,2,5,5,5] -> 可以拼成一个正方形
 *
 * @author Liaorun
 */
public class MatchSticks {

    public static void main(String[] args) {
        System.out.println(makeSquare(new int[]{3, 2, 5, 5, 5}));
        System.out.println(makeSquareDp(new int[]{3, 2, 5, 5, 5}));
    }

    public static boolean makeSquare(int[] matchSticks) {

        int sum = 0;

        for (int item : matchSticks) {
            sum += item;
        }

        // 火柴的总长度必须可以整除4才可能拼成正方形
        if (sum % 4 == 0) {

            // 正方形的边长 = 周长 / 4
            int len = sum / 4;

            return process(matchSticks, 0, 0, len, 4);
        }

        return false;
    }

    /**
     * @param arr    所有的火柴长度
     * @param status 每个火柴是否已经使用了的状态
     * @param cur    当前边已经拼的长度
     * @param len    正方形的边长
     * @param edges  还需要拼几条边
     * @return
     */
    public static boolean process(int[] arr, int status, int cur, int len, int edges) {

        if (edges == 0) {
            // 所有的边都拼好了，能拼成一个正方形

            // 如果这时所有的火柴全部使用了，就符合题意了
            return (status == (1 << arr.length) - 1);
        }

        // 是否可以拼成正方形
        boolean ans = false;

        // 还没都搞定！
        // arr 中，还没有尝试的火柴！当前全尝试一遍
        for (int i = 0; i < arr.length; i++) {
            // i 号火柴是否已经使用了
            if ((status & (1 << i)) == 0) {
                // 当前火柴还没用，可以用
                // 已经拼的边的长度 + 当前火柴的长度 > 正方形的边长
                if (cur + arr[i] > len) {
                    // 当前火柴不能用，尝试下一个
                    continue;
                } else if (cur + arr[i] < len) {
                    // 已经拼的边的长度 + 当前火柴的长度 < 正方形的边长
                    ans |= process(arr, status | (1 << i), cur + arr[i], len, edges);
                } else {
                    // 已经拼的边的长度 + 当前火柴的长度 = 正方形的边
                    // 拼好了一个边 edges - 1
                    ans |= process(arr, status | (1 << i), 0, len, edges - 1);
                }


                if (ans) {
                    // 找到一种解法即可跳出
                    break;
                }
            }
        }


        return ans;
    }


    public static boolean makeSquareDp(int[] matchSticks) {

        int sum = 0;

        for (int matchStick : matchSticks) {
            sum += matchStick;
        }

        // 火柴的总长度必须可以整除4才可能拼成正方形
        if ((sum & 3) != 0) {
            // 低二位必须是0 才能被4正常
            // 也可以写成 sum % 4 == 0
            return false;
        }

        int[] dp = new int[1 << matchSticks.length];

        return process(matchSticks, 0, 0, sum >> 2, 4, dp);
    }

    private static boolean process(int[] arr, int status, int cur, int len, int edges, int[] dp) {

        if (dp[status] != 0) {
            return dp[status] == 1;
        }

        boolean ans = false;

        if (edges == 0) {
            // 所有的边都拼好了，能拼成一个正方形
            // 如果这时所有的火柴全部使用了，就符合题意了
            ans = (status == (1 << arr.length) - 1);
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (((1 << i) & status) == 0 && cur + arr[i] <= len) {
                    if (cur + arr[i] == len) {
                        // 已经拼的边的长度 + 当前火柴的长度 = 正方形的边
                        // 拼好了一个边 edges - 1
                        ans |= process(arr, status | (1 << i), 0, len, edges - 1, dp);
                    } else {
                        // 已经拼的边的长度 + 当前火柴的长度 < 正方形的边长
                        // 使用当前边，在尝试拼剩下的部分
                        ans |= process(arr, status | (1 << i), cur + arr[i], len, edges, dp);
                    }
                }
                // 当前火柴不能用，尝试下一个
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }

}
